# June 2016, Dominik Peters
# Go through all weighted majority tournaments for up to 11 voters to check
# whether participation function satisfies participation

import ast
import gc

# readable alternative names
A,B,C,D = 0,1,2,3
string2alt = {"A": A, "B": B, "C": C, "D": D}

# a weighted tournament on 4 alternatives is represented by a 6-tuple;
# each coordinate is the weight of one of the edges, between -n and n;
# edges are in order: ab,ac,ad,bc,bd,cd
# ab = 6 means net 6 voters prefer a to b
votes = [(1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 1, -1), (1, 1, 1, -1, 1, 1), (1, 1, 1, -1, -1, 1), (1, 1, 1, 1, -1, -1), (1, 1, 1, -1, -1, -1), (-1, 1, 1, 1, 1, 1), (-1, 1, 1, 1, 1, -1), (-1, -1, 1, 1, 1, 1), (-1, -1, -1, 1, 1, 1), (-1, 1, -1, 1, 1, -1), (-1, -1, -1, 1, 1, -1), (1, -1, 1, -1, 1, 1), (1, -1, 1, -1, -1, 1), (-1, -1, 1, -1, 1, 1), (-1, -1, -1, -1, 1, 1), (1, -1, -1, -1, -1, 1), (-1, -1, -1, -1, -1, 1), (1, 1, -1, 1, -1, -1), (1, 1, -1, -1, -1, -1), (-1, 1, -1, 1, -1, -1), (-1, -1, -1, 1, -1, -1), (1, -1, -1, -1, -1, -1), (-1, -1, -1, -1, -1, -1)]

# in a vote given by a tournament, is x ranked above y?
def better(vote,x,y):
    (ab,ac,ad,bc,bd,cd) = vote
    if x == A and y == B:
        return ab > 0
    elif x == A and y == C:
        return ac > 0
    elif x == A and y == D:
        return ad > 0
    elif x == B and y == C:
        return bc > 0
    elif x == B and y == D:
        return bd > 0
    elif x == C and y == D:
        return cd > 0
    elif x == B and y == A:
        return ab < 0
    elif x == C and y == A:
        return ac < 0
    elif x == D and y == A:
        return ad < 0
    elif x == C and y == B:
        return bc < 0
    elif x == D and y == B:
        return bd < 0
    elif x == D and y == C:
        return cd < 0
    else:
        return False

# calculate the condorcet winner of a given tournament
def a_is_winner((ab,ac,ad,bc,bd,cd)):
    return ab > 0 and ac > 0 and ad > 0
def b_is_winner((ab,ac,ad,bc,bd,cd)):
    return ab < 0 and bc > 0 and bd > 0
def c_is_winner((ab,ac,ad,bc,bd,cd)):
    return ac < 0 and bc < 0 and cd > 0
def d_is_winner((ab,ac,ad,bc,bd,cd)):
    return ad < 0 and bd < 0 and cd < 0

# add two tournaments together (component-wise)        
def add(t1,t2):
    return tuple(sum(x) for x in zip(t1, t2))

# returns whether e weakly wants to participate given t                
def participation(t,e,t_plus_e,f):
    return f(t_plus_e) == f(t) or better(e,f(t_plus_e),f(t))


print "Reading input file.."
file = open("good_function_resolute_11.txt", "r")
function = {}
for i, line in enumerate(file):
    alt = string2alt[line[0]]
    tour = line[line.index('('):]
    tour = ast.literal_eval(tour)
    function[tour] = alt

def test_function((n, tour)):
    if a_is_winner(tour):
        return A
    elif b_is_winner(tour):
        return B
    elif c_is_winner(tour):
        return C
    elif d_is_winner(tour):
        return D
    else:
        return function[tour]

def check_participation(n,f):
    current_layer = [(1,vote) for vote in votes]
    for layer in range(1,n):
        print "Exploring layer ", layer
        next_layer = set()
        for t in current_layer:
            for e in votes:
                t_plus_e = (layer+1, add(t[1], e))
                next_layer.add(t_plus_e)
                if not participation(t,e,t_plus_e,f):
                    print "Participation Failure Found"
        current_layer = next_layer
        gc.collect()

check_participation(11,test_function)